/* 
    归并排序
    1.将序列中待排序数字分为若干组，每个数字分为一组
    2.将若干组两两组合，保证合并后的组是有序的
    3.重复第二步操作直到剩下一组，排序完成
*/
/* 自上而下 */
const mergeSort = (arr) => {
	var len = arr.length
	if (len < 2) {
		return arr
	}
	var middle = Math.floor(len / 2),
		left = arr.slice(0, middle),
		right = arr.slice(middle)
	return merge(mergeSort(left), mergeSort(right))
}
const merge = (left, right) => {
	let result = []
	while (left.length && right.length) {
		// 比较左右序列得首个数字
		if (left[0] <= right[0]) {
			result.push(left.shift())
		} else {
			result.push(right.shift())
		}
	}
	//如果有剩余，直接加入 left => right
	while (left.length) {
		result.push(left.shift())
	}
	while (right.length) {
		result.push(right.shift())
	}
	return result
}

const arr = mergeSort([1, 5, 2, 7, 0, 10])
console.log('quickSort :>>', arr)
